#! /usr/bin/env python3
# -*- coding: utf-8 -*-

"""
单向链表实现
"""


class Node:
    """
    存放节点类
    每次调⽤该类，实例化⼀个节点
    默认每个节点中有数据区，next区。
    数据区为该数据，next区为空
    """

    def __init__(self, item, next=None):
        self.item = item
        self.next = next


class SingleLinklist:
    def __init__(self, head=None):
        self.head = head

    def is_empty(self):
        if not self.head:
            return True
        return False

    def append(self, item):
        """
        往链表尾部添加数据
            1、实例化游标：使⽤游标指向每⼀个数据，检索数据和判断数据next是否为空
            2、移动游标，从头节点开始，每次使⽤self.next移动，以为next指向的就是下⼀个数据
            3、添加数据，⾸先判断链表是否为空，为空的情况下，直接将头节点等于node数据
            4、如果不为空，需要从头节点开始，移动游标，判断游标指向的next是否为空
            5、使⽤循环不停的移动节点，当遇到节点中的next为空的情况下停⽌移动
            6、循环条件：当条件 != None, 进⼊循环获取，当cur为空时就不会进⼊循环，所以在这⾥要使⽤ cur != None
        """

        # 实例化一个节点
        node = Node(item)
        # 判断链表是否为空链表
        if self.is_empty():
            # 直接将该节点设置为头结点
            self.head = node
            return

        # 实例化一个游标
        cur = self.head
        while cur.next:
            # 移动游标，得到最后一个游标的数据
            cur = cur.next
        # 将移动后的数据的下一个next添加上node
        cur.next = node

    def tarvel(self):
        """遍历链表"""
        # 实例化一个游标
        cur = self.head
        # 链表可能是空链表
        if self.is_empty():
            print("该链表为空链表！！！")
            return

        # 获取每个node的数据
        # 移动游标，输出node内的数据
        while cur:
            print(cur.item, end=' ')
            cur = cur.next
        print()

    def length(self):
        """返回链表的长度"""
        # 实例化游标
        cur = self.head
        # 计数
        count = 0
        while cur:
            count += 1
            # 移动游标
            cur = cur.next
        return count

    def add(self, item):
        """
        头部添加数据
        分析：将数据添加到第⼀个节点当中
        1、需要先将node的next指向原第⼀个节点，这原第⼀个节点就是self.head
        2、再讲self.head指向node进⾏连接
        """

        # 先实例化节点
        node = Node(item)
        # 将新节点的next指向头节点
        node.next = self.head
        # node成为链表新的头结点
        self.head = node

    def insert(self, index, item):
        """
        指定位置添加数据
        分析：
        1、⾸先要找到，该位置的数据
        2、将要添加的数据next等于原位置的next数据
        :param index: 节点索引位置
        :param item: 节点数据
        :return:
        """
        # index小于等于0，认为使从头部插入数据
        if index <= 0:
            self.add(item)

        # index大于链表长度，认为从链表尾部插入
        elif index > self.length():
            self.append(item)

        else:
            # 实例化数据节点
            node = Node(item)
            # 首先需要找到数据的位置
            # 实例化一个游标
            cur = self.head
            # 计数
            conent = 0
            while conent < index - 1:
                conent += 1
                cur = cur.next

            node.next = cur.next
            cur.next = node

    def search(self, item):
        """
        查询指定的数据是否存在，并返回索引位置
        分析：查询指定的数据，需要对整个链表扫描，判断这个数据是否等的该节点中的数据
        :param item: 数据
        :return:
        """

        # 实例化一个游标
        cur = self.head
        index = 0
        while cur:
            if cur.item == item:
                return index
            index += 1
            cur = cur.next

        return None

    def remove(self, item):
        """
        移除指定的数据
        分析：
        1、删除数据，需要⾸先判断数据是否存在
        2、找到该数据所在的位置，将该数据的上⼀个数据的next指向⾃⼰的next
        3、如何获取该数据的指向，和上⼀个数据的指向
        4、需要定义两个指针
        5、先将两个指针相等，再讲⼀个指针先移动⼀次，再同时移动
        """
        # 判断数据是否存在于链表内
        if not self.search(item):
            return False

        # 先找到该数据
        cur = self.head
        # 记录上被删除节点的上一个节点
        prev = None
        while cur:
            if cur.item == item:
                # 判断是否是头结点
                if cur == self.head:
                    self.head = cur.next
                else:
                    prev.next = cur.next
                break
            else:
                prev = cur
                cur = cur.next

    def reverse(self):
        """
        单链表逆序
        """
        # 实例化一个游标
        cur = self.head
        prev = None
        while cur:
            if cur.next is None:
                self.head = cur
            temp = cur.next
            cur.next = prev
            prev = cur
            cur = temp


if __name__ == '__main__':
    s = SingleLinklist()
    s.append(100)
    s.append(200)
    s.append(300)
    s.tarvel()
    print(s.length())
    s.insert(2, 50)
    s.tarvel()
    print(s.search(300))
    # s.remove(50)
    s.tarvel()
    s.reverse()
    s.tarvel()
